package com.facebook.app.server.clustering;

import java.util.ArrayList;
import java.util.List;

import com.facebook.app.shared.clustering.Clusterable;
import com.facebook.app.shared.clustering.Centroid;

public class KMeansClustering implements ClusteringStrategy {

	public static final int AVERAGE_NUMBER_OF_ELEMENTS_PER_CENTROID = 5;
	
	private final ClusterSimilarityStrategy similarityStrategy;

	private List<Clusterable> clusterElements;
	private List<Centroid> centroids;

	private int[] centroidIndexesOfClusterElements;

	public KMeansClustering(ClusterSimilarityStrategy similarityStrategy, List<Clusterable> clusterElements) {
		
		this.similarityStrategy = similarityStrategy;

		if (clusterElements instanceof ArrayList) {
			this.clusterElements = clusterElements;
		} else {
			this.clusterElements = new ArrayList<Clusterable>(clusterElements);
		}

		createCentroids();
	}

	private void createCentroids() {

		int numberOfCentroids = clusterElements.size()
				/ AVERAGE_NUMBER_OF_ELEMENTS_PER_CENTROID;

		centroids = new ArrayList<Centroid>(numberOfCentroids);

		centroidIndexesOfClusterElements = new int[clusterElements.size()];

		int characteristicClusterVectorSize = 0;

		if (clusterElements.size() > 0) {
			characteristicClusterVectorSize = clusterElements.get(0)
					.getCharacteristicClusterVector().length;
		}

		double[][] characteristicClusterVectors = new double[numberOfCentroids][characteristicClusterVectorSize];

		for (int i = 0; i < characteristicClusterVectors.length; i++) {
			for (int likeIndex = i; likeIndex < characteristicClusterVectors[i].length; likeIndex += characteristicClusterVectors.length) {
				characteristicClusterVectors[i][likeIndex] = 1;
			}

			centroids.add(new Centroid(characteristicClusterVectors[i]));
		}
	}

	@Override
	public List<Clusterable> createClusters() {

		if (centroids.size() < 2) {
			if (centroids.size() == 0) {
				int characteristicClusterVectorSize = 0;
				
				if (clusterElements.size() > 0) {
					characteristicClusterVectorSize = clusterElements.get(0)
					.getCharacteristicClusterVector().length;
				}
				centroids.add(new Centroid(new double[characteristicClusterVectorSize]));
			}
			centroids.get(0).addAllElementsAndAdaptVector(clusterElements);
			return new ArrayList<Clusterable>(centroids);
		}

		boolean clusteringFinished = false;
		boolean firstIteration = true;

		while (!clusteringFinished) {
			clusteringFinished = true;

			int currentClusterElementIndex = 0;
			for (Clusterable element : clusterElements) {
				double maxSimilarityScore = Double.NEGATIVE_INFINITY;
				double currentSimilarityScore;
				int indexOfCentroidWithMaxSimilarity = 0;

				int currentCentroidIndex = 0;
				for (Centroid centroid : centroids) {
					if ((currentSimilarityScore = similarityStrategy.computeSimilarity(element,
							centroid)) > maxSimilarityScore) {
						maxSimilarityScore = currentSimilarityScore;
						indexOfCentroidWithMaxSimilarity = currentCentroidIndex;
					}
					currentCentroidIndex++;
				}

				if (firstIteration
						|| indexOfCentroidWithMaxSimilarity != centroidIndexesOfClusterElements[currentClusterElementIndex]) {
					if (!firstIteration) {
						centroids
								.get(centroidIndexesOfClusterElements[currentClusterElementIndex]).removeElementAndAdaptVector(element);
					}

					centroids.get(indexOfCentroidWithMaxSimilarity).addElementAndAdaptVector(element);
					centroidIndexesOfClusterElements[currentClusterElementIndex] = indexOfCentroidWithMaxSimilarity;

					clusteringFinished = false;
				}
				currentClusterElementIndex++;
			}

			if (firstIteration) {
				firstIteration = false;
			}
		}
		return new ArrayList<Clusterable>(centroids);
	}

}
